1. Field of the Invention
The present invention relates to a decoding method. More particularly, the present invention relates to a sequential decoding method.
2. Description of Related Art
In a communication system, channel coding is required for baseband signal processing of a data to reliably transmit the data to a receiver through a channel. Existing channel coding usually includes more than two types of coding. FIG. 1 is a block diagram illustrating the channel coding at a transmitter according to a conventional technique.
Referring to FIG. 1, a message sequence b is first encoded into a first codeword V by an external encoder 110, then encoded into a second codeword u by an internal encoder 120, and modulated by a modulation unit 130 before it is transmitted into a channel. The aforementioned external encoder can be implemented with an error detection code, wherein the error detection code may be a cyclic redundancy check  (CRC) code or a parity check code. The aforementioned internal encoder can be implemented with an error correction code, wherein the error correction code may be a trellis code which encodes or decodes through a trellis diagram, and the commonest trellis code is convolution code.
Corresponding to the transmitter, the received signal r received at the receiver through the channel has to be demodulated, internally decoded, and externally decoded to obtain a final output codeword {circumflex over (b)} (if no error occurs, the final output codeword {circumflex over (b)} is the message sequence b).
The “Generalized Viterbi Decoding Algorithms” provided by the U.S. Pat. No. 5,208,816 and the article “List Viterbi Decoding Algorithm with Application” published by Nambirajan Seshadri and Carl-erik W. Sundberg in “Transactions on Communications” Vol. 42, No. 2/3/4, 1994 issued by the Institute of Electrical and Electronic Engineers (IEEE) among conventional techniques have provided methods for decoding to obtain the final output codeword {circumflex over (b)} at the receiver by using Viterbi decoding and trellis diagram. Wherein Viterbi decoding is further divided into parallel Viterbi decoding and serial Viterbi decoding. FIG. 2 is a block diagram illustrating the parallel Viterbi decoding at a receiver according to a conventional technique, and FIG. 3 is a block diagram illustrating the serial Viterbi decoding at a receiver according to a conventional technique.
Referring to FIG. 2 first, the received signal r is demodulated into a first output codeword û by a demodulation unit 210 and is then sent to an internal decoder 220. The internal decoder 220 determines L paths similar to the first output codeword û through a trellis diagram and outputs L second output codewords  {circumflex over (v)}[1], {circumflex over (v)}[2] . . . {circumflex over (v)}[L] respectively corresponding to L paths to an external decoder 230. Wherein the second output codeword corresponding to the path having the maximum likelihood is {circumflex over (v)}[1] the second output codeword corresponding to the path having the second likelihood is {circumflex over (v)}[2], and so on. The second output codewords are organized as {circumflex over (v)}[1],{circumflex over (v)}[2], . . . {circumflex over (v)}[L] according to the likelihood thereof which is calculated with a metric. After the external decoder 230 receives the L second output codewords {circumflex over (v)}[1], {circumflex over (v)}[2], . . . {circumflex over (v)}[L], the external decoder 230 sequentially determines whether the redundancy in the second output codewords are correct and obtains the final output codeword {circumflex over (b)} through the second output codewords {circumflex over (v)}[1], {circumflex over (v)}[2], . . . {circumflex over (v)}[L]
Referring to FIG. 3, the received signal r is demodulated into a first output codeword û by a demodulation unit 310 and is then sent to an internal decoder 320. The internal decoder 320 determines the path having the maximum likelihood through a trellis diagram and outputs a second output codeword {circumflex over (v)} corresponding to the path having the maximum likelihood to an external decoder 330. The external decoder 330 determines whether the redundancy in the second output codeword {circumflex over (v)} is correct. If the redundancy in the second output codeword {circumflex over (v)} are correct, the external decoder 330 decodes the second output codeword {circumflex over (v)} into the final output codeword {circumflex over (b)}, otherwise, the external decoder 330 requests the internal decoder 320 to output another second output codeword v. The internal decoder 320 then determines the path having the second likelihood through the trellis diagram and outputs a second output codeword {circumflex over (v)} corresponding to the path having the second likelihood to the  external decoder 330. As described above, the internal decoder 320 and the external decoder 330 work together to obtain the final output codeword {circumflex over (b)}.
However, during the parallel Viterbi decoding procedure, the metrics of extended successor paths on every state of every level of the trellis diagram have to be stored and calculated to determines the L similar paths. Thus, in actual application, a lot of calculations are required by parallel Viterbi decoding to output L second output codewords. Besides, in parallel Viterbi decoding, the metrics of the successor paths of all the nodes in the trellis diagram have to be calculated and L second output codewords have to be output to the external decoder regardless of the situation of the channel. Thus, the large quantity of calculation cannot be reduced in parallel Viterbi decoding even when the channel is in very good quality.
As to serial Viterbi decoding, in actual application, a lot of calculations are still required for calculating and storing the metrics of the successor paths extended from all the nodes even though only one second output codeword is output every time. Besides, before the final output codeword {circumflex over (b)} is determined, the internal decoder has to start off from the origin node of the trellis diagram and decides an existence path on every state once again to output another second output codeword whenever the external decoder determines that the second output codeword is incorrect. Thus, if serial Viterbi decoding is implemented with hardware, a lot of memory space is required by the internal decoder for storing the metrics of all the paths in the trellis diagram, so as to provide different second output codewords. 